package com.zwy.leetcode;

import java.util.*;

public class Day11Test {
    //面试题 17.16. 按摩师
    public int massage(int[] nums) {
        if(nums.length==1)return nums[0];
        if(nums.length==0)return 0;
        int []dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=nums[0]>nums[1]?nums[0]:nums[1];
        for (int i = 2; i <nums.length ; i++) {
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[dp.length-1];
    }

    /**
     *  K 次串联后最大子数组之和
     * @param arr
     * @param k
     * @return
     */
    public int kConcatenationMaxSum(int[] arr, int k) {
        int length=arr.length*2;
        if(k==1)length=length/2;
        int []arr2=new int[length];
        int []dp=new int[length];
        int []dp2=new int[arr.length];
        long max=arr[0];
        long sum=0;
        long maxSum=arr[0];

        for (int i = 0; i <arr.length ; i++) {
            sum+=arr[i];
            maxSum=Math.max(maxSum,sum);
        }
        if(sum<=0) {
            for (int i = 0; i < arr2.length; i++) {
                if (i < arr.length)
                    arr2[i] = arr[i];
                else
                    arr2[i] = arr[i - arr.length];
            }
            dp[0] = arr2[0];
            for (int i = 1; i < dp.length; i++) {
                if (dp[i - 1] < 0) dp[i] = arr2[i];
                else dp[i] = dp[i - 1] + arr2[i];
                max = Math.max(max, dp[i]);
            }
        }
        else{
            int sum2=0;
            dp2[0] = arr[0];
            for (int i = arr.length-1; i >=0; i--) {
                 sum2+=arr[i];
                max = Math.max(sum2, max);
            }
            max+=sum*(k-2)+maxSum;
        }
        if(max<0&&sum*k<0)return 0;
        long res=0;
        if(max>sum*k)res=max%1000000007;
        else  res=(sum*k)%1000000007;
        return (int)res;
    }

    /**
     * 1669. 合并两个链表
     * @param list1
     * @param a
     * @param b
     * @param list2
     * @return
     */
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        int current=0;
        ListNode p1=list1;
        ListNode p2=list2;
        ListNode p4=list2;
        ListNode p3=null;
        while(p4.next!=null){
            p4=p4.next;
        }

        while (current<b+1){
            if(current<a-1){
                p1=p1.next;
            }
            else if(current==a-1){
                 p3=p1.next;
                p1.next=list2;
            }
            else{
               p3=p3.next;
               if(current==b){
                   p4.next=p3;
                   break;
               }
            }
            current++;
        }
        return list1;
    }


    public boolean judgeCircle(String moves) {
        int leftNum=0;
        int rightNum=0;
        int downNum=0;
        int upNum=0;
        for (int i = 0; i < moves.length(); i++) {
            if(moves.charAt(i)=='U')upNum++;
            if(moves.charAt(i)=='D')downNum++;
            if(moves.charAt(i)=='L')leftNum++;
            if(moves.charAt(i)=='R')rightNum++;
        }
        if(upNum==downNum&&leftNum==rightNum)return true;
        return false;
    }

    /**
     *剑指 Offer II 012. 左右两边子数组的和相等
     * @param nums
     * @return
     */
    public int pivotIndex(int[] nums) {
        int sum=0;
        int t=0;
        int prev=0;
        for (int i = 0; i <nums.length ; i++) {
            sum+=nums[i];
        }
        if(sum-nums[0]==0)return 0;
        for (int i = 0; i < nums.length; i++) {
            prev=t;
            t+=nums[i];
            if(sum-nums[i]==prev*2)return i;
        }
        return -1;
    }

    /**
     * 1128. 等价多米诺骨牌对的数量
     * @param dominoes
     * @return
     */
    public int numEquivDominoPairs(int[][] dominoes) {
        Map<String,Integer> map=new HashMap<String,Integer>();
        int count=0;
        String s="";
        for (int i = 0; i < dominoes.length; i++) {
            Arrays.sort(dominoes[i]);
            s=dominoes[i][0]+""+dominoes[i][1];
            if(!map.containsKey(s))
            map.put(s,1);
            else{
                Integer integer = map.get(s);
                map.put(s,integer+1);
            }
        }
        Set<String> set = map.keySet();
        for (String s1 : set) {
            Integer integer = map.get(s1);
            count+=integer*(integer-1)/2;
        }
        return count;
    }

    /**
     * 面试题 17.04. 消失的数字
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int length=nums.length;
        int sum=(length)*(length+1)/2;
        int count=0;
        for (int i = 0; i < length; i++) {
            count+=nums[i];
        }
        return sum-count;
    }
    public static void main(String[] args) {
       int []arr={9,6,4,2,3,5,7,0,1};
        Day11Test test=new Day11Test();
        int i = test.missingNumber(arr);
        System.out.println(i);

    }
}
